// 编写一个程序，通过填充空格来解决数独问题。
// 一个数独的解法需遵循如下规则： 
// 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
// 给定的数独序列只包含数字 1-9 和字符 '.' 。
// 你可以假设给定的数独只有唯一解。
// 给定数独永远是 9x9 形式的
function solveSudoku(board) {
    function backtracking() {
        for (let i = 0; i < board.length; i++) {
            for (let j = 0; j < board[0].length; j++) {
                if (board[i][j] === '.') {
                    for (let k = 1; k <= 9; k++) {
                        let val = String(k)
                        if (isValid(i, j, val, board)) {
                            board[i][j] = val
                            if (backtracking()) {
                                return true
                            }
                            board[i][j] = '.'
                        }                    
                    }
                    // 遍历完1-9都不对，那直接返回false
                    return false
                }            
            }        
        }
        return true
    }
    function isValid(row, col, val, board) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === val) {
                return false
            }            
        }
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === val) {
                return false
            }            
        }
        // 这里注意如何计算3 * 3的小方格
        let startRow = Math.floor(row / 3) * 3
        let startCol = Math.floor(col / 3) * 3
        for (let i = startRow; i < startRow + 3; i++) {
            for (let j = startCol; j < startCol + 3; j++) {
                if (board[i][j] === val) {
                    return false
                }                
            }            
        }
        return true
    }
    backtracking()
    return board
}

let board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
console.log(solveSudoku(board))